'''
Created on 2011-5-31

@author: elm
'''
import xmlrpclib,random,time
from ddbms.RelationalAlgebra import *
from ddbms.Schema import *
from ddbms.SqlStatement import *
from ddbms.DdbmsException import *
from ddbms.Json import read,dump
from ddbms.URIUtil import parseConn
from ddbms.Dataset import Dataset, DeferredDataset
import MySQLdb as mdb

class ExecuterSite:    
    schema = None
    mysql = None
    def __init__(self,schema,mysql):
        self.schema = schema
        self.mysql = mysql        
        self.checkSchema()
    
    def fetchSegment(self,seg,conn):
        myId = self.schema.siteId
        fromSiteId = None
        for siteId in seg.sites:
            if myId != siteId:
                fromSiteId = siteId
        if fromSiteId != None:
            print ("Segment #%d missed, trying to fetch it from site%d"%(seg.id,fromSiteId))
        else:
            print ("Segment #%d missed and can't find it from other site")
            return
        table = self.schema.findTable(seg.table)
        raseg = TableSegment(seg.name, 0, seg.id)
        raseg.executionSite = fromSiteId
        data = self.findAndExecute(raseg)
        cursor = conn.cursor()
        cursor.execute("DROP TABLE IF EXISTS %s"%seg.name)
        cols = []
        icols = []  
        tcols = []      
        for colId in seg.columns:
            col = self.schema.findColumn(colId)
            colstr = "`%s` %s(%d)"%(col.name,col.type,col.length)
            cols.append(colstr)
            icols.append(col.name)
            tcols.append("%s.%s"%(table.name,col.name))
        sql =""          
        if table.primaryKey != None:
            sql = """CREATE TABLE IF NOT EXISTS %s (
                %s, PRIMARY KEY (%s)
            )"""%(seg.name,",".join(cols),table.primaryKey)
        else:
            sql = """CREATE TABLE IF NOT EXISTS %s (
                %s
            )"""%(seg.name,",".join(cols))
        cursor.execute(sql)                    
        for d in data.dataset:
            tp = []
            for tk in tcols:
                if isinstance(d[tk],str):
                    tp.append("'%s'"%(d[tk]).replace("'", "''"))
                else:
                    tp.append(str(d[tk]))            
            sql = "INSERT INTO %s (%s) VALUES (%s)"%(seg.name,",".join(icols),",".join(tp))
            print(sql)
            cursor.execute(sql)
        seg.length = len(data.dataset)
        cursor.execute("commit")
        print ("Segment #%d fetched"%seg.id)
            
    def checkSchema(self):
        if self.schema == None:
            return
        myId = self.schema.siteId
        mySite = self.schema.sites[myId]
        (host,user,pwd,db) = self.mysql
        conn = mdb.connect(host, user, pwd, db)
        cursor = conn.cursor()
        for segId in mySite.segments:
            seg = self.schema.segments[segId]
            succ = False
            try:
                checkSql = "select count(*) from %s"%seg.name
                cursor.execute(checkSql)
                c = cursor.fetchall()
                count = c[0][0]
                succ = count > 0
                seg.length = count
            except:
                succ = False
            if not succ:                
                self.fetchSegment(seg,conn)
        
    def toRA(self,statement):
        fieldrefs = statement.fieldrefs
        tablerefs = statement.tablerefs    
        conditions = statement.condition.conditions
        tablemap = {}
        for tableref in tablerefs:
            tablemap[tableref.table] = RATable(tableref.table)
        joins = []
        
        for cond in conditions:
            if(isinstance(cond,TestField) 
               and cond.leftfieldref!=cond.rightfieldref):
                'A join operation'
                lefttable=tablemap[cond.leftfieldref.table.table]
                righttable=tablemap[cond.rightfieldref.table.table]
                leftkey = cond.leftfieldref
                rightkey = cond.rightfieldref
                if(lefttable!=righttable):
                    'a join operator must joins two distinct tables'
                    joins=joins+[cond]
                    j = Join(lefttable,righttable,leftkey,rightkey)
                    joined=filter(
                        lambda x:
                            tablemap[x]==lefttable
                            or tablemap[x]==righttable
                        , tablemap)
                    for k in joined:
                        tablemap[k] = j
        
        distinctTables = []
        for x in tablemap:
            t = tablemap[x]
            found = False
            for dt in distinctTables:
                if (dt==t):
                    found = True
                    break
            if (not found):
                distinctTables=distinctTables+[t]
        
        root = reduce(lambda x,y:Product(x,y),distinctTables)
        selects = filter(lambda x:joins.count(x)==0,conditions)
        root = reduce(lambda x,y:Select(x,y),selects,root)
        if not isinstance(fieldrefs,FieldRefAll):
            root = Projection(root,
                              fieldrefs)
                        
        return root
    
    def parse(self,sql):
        sqlstatement = SqlStatement()
        statement = sqlstatement.parse(sql)
        tables = []
        for tableref in statement.tablerefs:
            table = self.schema.findTable(tableref.table)
            if(table == None):
                raise TableNotFound
            tables +=[table]
        if not isinstance(statement.fieldrefs,FieldRefAll):
            for fieldref in statement.fieldrefs:
                if not isinstance(fieldref,FieldRefAll):
                    if fieldref.table == None:
                        found = None
                        for table in tables:
                            if(self.schema.findColumn(table,fieldref.column)!=None):
                                if found == None:
                                    found = table
                                else:
                                    raise AmbiguousColumn                        
                        if found == None:
                            raise ColumnNotFound
                        else:
                            fieldref.table = TableRef(found.name)
        def refineCondition(cond):
            '''
            If the table name is omitted in sql statement,
            this function will try to recover the table names.
            An exception will be thrown if the table
            can not be determined
            '''
            if isinstance(cond,Conjunction):
                for subcond in cond.conditions:
                    refineCondition(subcond)
            elif isinstance(cond,LogicalNot):
                refineCondition(cond.condition)
            elif isinstance(cond,LogicalAnd):
                refineCondition(cond.leftparam)
                refineCondition(cond.rightparam)
            elif isinstance(cond,LogicalOr):
                refineCondition(cond.leftparam)
                refineCondition(cond.rightparam)
            elif isinstance(cond,TestValue):
                fieldref = cond.fieldref
                if not isinstance(fieldref,FieldRefAll):
                    if fieldref.table == None:
                        found = None
                        for table in tables:
                            if(self.schema.findColumn(table,fieldref.column)!=None):
                                if found == None:
                                    found = table
                                else:
                                    raise AmbiguousColumn                        
                        if found == None:
                            raise ColumnNotFound
                        else:
                            fieldref.table = TableRef(found.name)
            elif isinstance(cond,TestField):
                fieldref = cond.leftfieldref
                if not isinstance(fieldref,FieldRefAll):
                    if fieldref.table == None:
                        found = None
                        for table in tables:
                            if(self.schema.findColumn(table,fieldref.column)!=None):
                                if found == None:
                                    found = table
                                else:
                                    raise AmbiguousColumn                        
                        if found == None:
                            raise ColumnNotFound
                        else:
                            fieldref.table = TableRef(found.name)
                fieldref = cond.rightfieldref
                if not isinstance(fieldref,FieldRefAll):
                    if fieldref.table == None:
                        found = None
                        for table in tables:
                            if(self.schema.findColumn(table,fieldref.column)!=None):
                                if found == None:
                                    found = table
                                else:
                                    raise AmbiguousColumn                        
                        if found == None:
                            raise ColumnNotFound
                        else:
                            fieldref.table = TableRef(found.name)
            else:
                raise InvalidCondition
        refineCondition(statement.condition)
        return self.toRA(statement)
    
    def getRAColumns(self,ra):
        if isinstance(ra,Projection):
            cols = self.getRAColumns(ra.input)
            selcols = set()         
            for colid in cols:
                for fieldref in ra.fields:
                    referredCol = self.schema.findColumn(fieldref.table.table,fieldref.column)
                    if(referredCol != None):
                        if(colid == referredCol.id):
                            selcols.add(colid)
                            break
            return selcols
        elif isinstance(ra,Select):
            return self.getRAColumns(ra.input)
        elif isinstance(ra,Join):
            leftcols = self.getRAColumns(ra.lefttable)
            rightcols = self.getRAColumns(ra.righttable)            
            return leftcols.union(rightcols)
        elif isinstance(ra,Union):
            return self.getRAColumns(ra.lefttable)
        elif isinstance(ra,Product):
            leftcols = self.getRAColumns(ra.lefttable)
            rightcols = self.getRAColumns(ra.righttable)
            return leftcols.union(rightcols)
        elif isinstance(ra,RATable):
            table = self.schema.findTable(ra.name)
            return set(table.columns)
        elif isinstance(ra,TableSegment):
            ts = self.schema.findSegment(ra.id)
            return set(ts.columns)
        else:
            raise InvalidRA
    
    def getRAConditions(self,ra):
        if isinstance(ra,Projection):
            return self.getRAConditions(ra.input)
        elif isinstance(ra,Select):
            c = self.getRAConditions(ra.input)
            if c!=None:
                return LogicalAnd(c,ra.condition).toCNF()
            else:
                return ra.condition.toCNF()
        elif isinstance(ra,Join):
            lc = self.getRAConditions(ra.lefttable)
            rc = self.getRAConditions(ra.righttable)
            if lc == None and rc ==None:
                return None
            elif lc == None:
                return rc
            elif rc == None:
                return lc
            else:                
                return LogicalAnd(LogicalAnd(lc,rc),TestField(ra.leftkey,Ops.EQ,ra.rightkey)).toCNF()
            
        elif isinstance(ra,Union):
            lc = self.getRAConditions(ra.lefttable)
            rc = self.getRAConditions(ra.righttable)
            if lc == None or rc ==None:
                return None
            else:
                return LogicalOr(lc,rc).toCNF()
        elif isinstance(ra,Product):
            lc = self.getRAConditions(ra.lefttable)
            rc = self.getRAConditions(ra.righttable)
            if lc == None and rc ==None:
                return None
            elif lc == None:
                return rc
            elif rc == None:
                return lc
            else:
                return LogicalAnd(lc,rc).toCNF()
        elif isinstance(ra,RATable):
            return None
        elif isinstance(ra,TableSegment):
            cond = ra.condition
            if(cond==None):
                return None
            else:
                return cond.toCNF()
        else:
            raise InvalidRA    
    def getLogicalReferredColumns(self,cond):
        if isinstance(cond,Conjunction):
            cols = set()
            for sc in cond.conditions:
                cols = cols.union(self.getLogicalReferredColumns(sc))
            return cols
        elif isinstance(cond,LogicalNot):
            return self.getLogicalReferredColumns(cond.condition)
        elif isinstance(cond,LogicalAnd):
            leftcols = self.getLogicalReferredColumns(cond.leftparam)
            rightcols = self.getLogicalReferredColumns(cond.rightparam)
            return leftcols.union(rightcols)             
        elif isinstance(cond,LogicalOr):
            leftcols = self.getLogicalReferredColumns(cond.leftparam)
            rightcols = self.getLogicalReferredColumns(cond.rightparam)
            return leftcols.union(rightcols)
        elif isinstance(cond,TestValue):
            fr = cond.fieldref
            col = self.schema.findColumn(fr.table.table,fr.column)
            return set([col.id])
        elif isinstance(cond,TestField):
            lfr = cond.leftfieldref
            rfr = cond.rightfieldref
            lcol = self.schema.findColumn(lfr.table.table,lfr.column)
            rcol = self.schema.findColumn(rfr.table.table,rfr.column)
            return set([lcol.id,rcol.id])
        else:
            raise InvalidCondition
    
    def expand(self,ra):
        if isinstance(ra,Projection):
            return Projection(self.expand(ra.input),ra.fields)
        elif isinstance(ra,Select):
            return Select(self.expand(ra.input),ra.condition)
        elif isinstance(ra,Join):
            return Join(self.expand(ra.lefttable),self.expand(ra.righttable),
                        ra.leftkey,ra.rightkey)
        elif isinstance(ra,Union):
            return Union(self.expand(ra.lefttable),self.expand(ra.righttable))
        elif isinstance(ra,Product):
            return Product(self.expand(ra.lefttable),self.expand(ra.righttable))
        elif isinstance(ra,RATable):
            '''
            Split a logical table to
            physical table segments
            '''
            table = self.schema.findTable(ra.name)
            if(table==None):
                raise TableNotFound
            segments = table.segments        
            if(len(segments)<=0):
                raise InvalidSchema
            s0 = self.schema.findSegment(segments[0])
            if isinstance(s0,HorizontalSegment):
                result = None
                for index in range(0,len(segments)):
                    segid = segments[index]
                    seg = self.schema.findSegment(segid)
                    tseg = TableSegment(table.name,index,segid,seg.segmentCondition)
                    if index == 0:
                        result = tseg
                    else:
                        result = Union(result, tseg)
                        result.segmentUnion=True
                return result
            elif isinstance(s0,VerticalSegment):
                result = None
                for index in range(0,len(segments)):
                    segid = segments[index]
                    seg = self.schema.findSegment(segid)
                    tseg = TableSegment(table.name,index,segid)
                    if index == 0:
                        result = tseg
                    else:
                        result = Join(result, tseg,
                                      FieldRef(TableRef(table.name) ,table.primaryKey),
                                      FieldRef(TableRef(table.name) ,table.primaryKey))
                        result.segmentJoin = True
                return result
            else:
                raise InvalidSegmentation
        else:
            raise InvalidRA

    def optimize(self,ra):
        def movedownSelect(ra):
            if isinstance(ra,Projection):
                ra.input = movedownSelect(ra.input)
            elif isinstance(ra,Select):
                ra.input = movedownSelect(ra.input)
                cra = ra.input
                cnf = ra.condition.toConjunction()
                if isinstance(cra,Projection):
                    'Do nothing'           
                elif isinstance(cra,Select): 
                    'Do nothing'
                elif isinstance(cra,Join) or isinstance(cra,Union) or isinstance(cra,Product): 
                    'move select to bottom of the join'
                    leftcols = self.getRAColumns(cra.lefttable)
                    rightcols = self.getRAColumns(cra.righttable)
                    leftcnf = Conjunction()
                    rightcnf = Conjunction()
                    outercnf = Conjunction()
                    for cond in cnf.conditions:
                        condcols = self.getLogicalReferredColumns(cond)
                        inouter = False
                        used = False
                        if condcols.issubset(leftcols):
                            leftcnf.conditions += [cond]
                            used = True
                        elif len(condcols.intersection(leftcols))>0:
                            inouter = True                            
                        if condcols.issubset(rightcols):
                            rightcnf.conditions += [cond]
                            used = True
                        elif len(condcols.intersection(rightcols))>0:
                            inouter = True                        
                        if inouter or not used:
                            outercnf.conditions += [cond]                    
                    if len(leftcnf.conditions)>0:
                        leftSel = Select(cra.lefttable,leftcnf)
                        cra.lefttable = movedownSelect(leftSel)
                    if len(rightcnf.conditions)>0:
                        rightSel = Select(cra.righttable,rightcnf)
                        cra.righttable = movedownSelect(rightSel)
                    if len(outercnf.conditions)>0:
                        ra.input = cra
                        ra.condition = outercnf
                    else:
                        ra = cra
                #elif isinstance(cra,Union): 
                #    'the same as Join'                    
                #elif isinstance(cra,Product):   
                #    'the same as Join'
                elif isinstance(cra,RATable):
                    'Do nothing'
                elif isinstance(cra,TableSegment):
                    'Do nothing'               
                else:
                    raise InvalidRA                
            elif isinstance(ra,Join):
                ra.lefttable = movedownSelect(ra.lefttable)
                ra.righttable = movedownSelect(ra.righttable)
            elif isinstance(ra,Union):
                ra.lefttable = movedownSelect(ra.lefttable)
                ra.righttable = movedownSelect(ra.righttable)
            elif isinstance(ra,Product):
                ra.lefttable = movedownSelect(ra.lefttable)
                ra.righttable = movedownSelect(ra.righttable)
            elif isinstance(ra,RATable):
                'this recursion has already got to the bottom'
                return ra
            elif isinstance(ra,TableSegment):
                'this recursion has already got to the bottom'
                return ra
            else:
                raise InvalidRA
            return ra
        def movedownProjection(ra):            
            if isinstance(ra,Projection):
                '''Move down projection'''
                cra = ra.input
                cols = self.getRAColumns(ra)
                if isinstance(cra,Projection):
                    'Do nothing'
                elif isinstance(cra,Select): 
                    'Move down projection, add select keys'
                    lcols = self.getRAColumns(cra.input)
                    lprojcols = cols.intersection(lcols)
                    lselectcols = self.getLogicalReferredColumns(cra.condition)
                    lprojcols = lprojcols.union(lselectcols)
                    lfields = []
                    for colid in lprojcols:
                        col = self.schema.findColumn(colid)
                        table = self.schema.findTable(col.table)
                        lfields += [FieldRef(TableRef(table.name),col.name)]
                    cra.input = movedownProjection(Projection(cra.input,lfields))
                    newcols= self.getRAColumns(cra)
                    cols = self.getRAColumns(ra)
                    if(cols == newcols):
                        ra = cra
                    else:
                        ra.input = cra
                    
                elif isinstance(cra,Join):
                    '''
                    Move down projection,
                    Add join key and keep outer projection
                    '''
                    lcols = self.getRAColumns(cra.lefttable)
                    rcols = self.getRAColumns(cra.righttable)
                    lprojcols = cols.intersection(lcols)
                    lprojcols.add(self.schema.findColumn(cra.leftkey).id)
                    rprojcols = cols.intersection(rcols)
                    rprojcols.add(self.schema.findColumn(cra.rightkey).id)
                    lfields = []
                    rfields = []
                    for colid in lprojcols:
                        col = self.schema.findColumn(colid)
                        table = self.schema.findTable(col.table)
                        lfields += [FieldRef(TableRef(table.name),col.name)]
                    for colid in rprojcols:
                        col = self.schema.findColumn(colid)
                        table = self.schema.findTable(col.table)
                        rfields += [FieldRef(TableRef(table.name),col.name)]
                    cra.lefttable = movedownProjection(Projection(cra.lefttable,lfields))
                    cra.righttable = movedownProjection(Projection(cra.righttable,rfields))
                    newcols= self.getRAColumns(cra)
                    cols = self.getRAColumns(ra)
                    if(cols == newcols):
                        ra = cra
                    else:
                        ra.input = cra
                elif isinstance(cra,Union) or isinstance(cra,Product): 
                    '''
                    Move down projection                    
                    '''
                    lcols = self.getRAColumns(cra.lefttable)
                    rcols = self.getRAColumns(cra.righttable)
                    lprojcols = cols.intersection(lcols)
                    rprojcols = cols.intersection(rcols)
                    lfields = []
                    rfields = []
                    for colid in lprojcols:
                        col = self.schema.findColumn(colid)
                        table = self.schema.findTable(col.table)
                        lfields += [FieldRef(TableRef(table.name),col.name)]
                    for colid in rprojcols:
                        col = self.schema.findColumn(colid)
                        table = self.schema.findTable(col.table)
                        rfields += [FieldRef(TableRef(table.name),col.name)]
                    cra.lefttable = movedownProjection(Projection(cra.lefttable,lfields))
                    cra.righttable = movedownProjection(Projection(cra.righttable,rfields))
                    newcols= self.getRAColumns(cra)
                    cols = self.getRAColumns(ra)
                    if(cols == newcols):
                        ra = cra
                    else:
                        ra.input = cra
                #elif isinstance(cra,Product): 
                #    'same with Union'
                elif isinstance(cra,RATable):
                    'Do nothing'
                elif isinstance(cra,TableSegment):
                    'Do nothing'               
                else:
                    raise InvalidRA 
            elif isinstance(ra,Select):
                ra.input = movedownProjection(ra.input)
            elif isinstance(ra,Join):
                ra.lefttable = movedownProjection(ra.lefttable)
                ra.righttable = movedownProjection(ra.righttable)             
            elif isinstance(ra,Union):
                ra.lefttable = movedownProjection(ra.lefttable)
                ra.righttable = movedownProjection(ra.righttable)                
            elif isinstance(ra,Product): 
                ra.lefttable = movedownProjection(ra.lefttable)
                ra.righttable = movedownProjection(ra.righttable)               
            elif isinstance(ra,RATable):
                'recursion terminated'              
            elif isinstance(ra,TableSegment):      
                'recursion terminated'               
            else:
                raise InvalidRA
            return ra
        def pruneSelect(ra):            
            if isinstance(ra,Projection):
                res = pruneSelect(ra.input)
                if res==None:
                    ra = None
                else:
                    ra.input = res     
            elif isinstance(ra,Select):
                res = pruneSelect(ra.input)
                if res==None:
                    ra = None
                else:
                    ra.input = res
                    cond = ra.condition.toCNF()
                    subcond = self.getRAConditions(ra.input)
                    if subcond != None and not LogicalAnd(cond,subcond).toCNF().sat():
                        ra = None
            elif isinstance(ra,Join):
                rl = pruneSelect(ra.lefttable)
                rr = pruneSelect(ra.righttable)
                if(rl==None or rr==None):
                    ra = None
                else:
                    ra.lefttable = rl
                    ra.righttable = rr
            elif isinstance(ra,Union):
                rl = pruneSelect(ra.lefttable)
                rr = pruneSelect(ra.righttable)
                if(rl==None and rr==None):
                    ra = None
                elif rl==None:
                    ra = rr
                elif rr==None:
                    ra = rl
                else:
                    ra.lefttable = rl
                    ra.righttable = rr                    
            elif isinstance(ra,Product):
                rl = pruneSelect(ra.lefttable)
                rr = pruneSelect(ra.righttable)
                if(rl==None or rr==None):
                    ra = None
                else:
                    ra.lefttable = rl
                    ra.righttable = rr
            elif isinstance(ra,RATable):
                'recursion terminated'                
            elif isinstance(ra,TableSegment):
                'recursion terminated'               
            else:
                raise InvalidRA
            return ra
        def pruneProjection(ra):
            if isinstance(ra,Projection):
                res = pruneProjection(ra.input)
                if res==None:
                    ra = None
                else:
                    ra.input = res
                    subcols = self.getRAColumns(ra.input)
                    cols = set()
                    for fieldref in ra.fields:
                        cols.add(self.schema.findColumn(fieldref).id)
                    if subcols.isdisjoint(cols):
                        ra = None
                    elif subcols == cols:
                        ra = ra.input
            elif isinstance(ra,Select):
                res = pruneProjection(ra.input)
                if res==None:
                    ra = None
                else:
                    ra.input = res
            elif isinstance(ra,Join):
                rl = pruneProjection(ra.lefttable)
                rr = pruneProjection(ra.righttable)
                if(rl==None or rr==None):
                    ra = None
                else:
                    ra.lefttable = rl
                    ra.righttable = rr
                    if ra.segmentJoin:
                        key = self.schema.findColumn(ra.leftkey).id
                        keyset = set([key])
                        leftset = self.getRAColumns(ra.lefttable)
                        rightset = self.getRAColumns(ra.righttable)
                        def isOriginTable(ra):
                            if isinstance(ra,Projection):
                                return isOriginTable(ra.input)
                            elif isinstance(ra,TableSegment) or isinstance(ra,RATable):
                                return True
                            else:
                                return False
                        if leftset == keyset and isOriginTable(ra.lefttable):                        
                            if rightset == keyset and isOriginTable(ra.righttable):
                                '''
                                TODO::determine which segment is reserved
                                according to their site
                                '''
                                ra = ra.lefttable
                            else:
                                ra = ra.righttable
                        else:
                            if rightset == keyset and isOriginTable(ra.righttable):
                                ra = ra.lefttable
                                
            elif isinstance(ra,Union):
                rl = pruneProjection(ra.lefttable)
                rr = pruneProjection(ra.righttable)
                if(rl==None and rr==None):
                    ra = None
                elif rl==None:
                    ra = rr
                elif rr==None:
                    ra = rl
                else:
                    ra.lefttable = rl
                    ra.righttable = rr                    
            elif isinstance(ra,Product):
                rl = pruneProjection(ra.lefttable)
                rr = pruneProjection(ra.righttable)
                if(rl==None or rr==None):
                    ra = None
                else:
                    ra.lefttable = rl
                    ra.righttable = rr
            elif isinstance(ra,RATable):
                'recursion terminated'                
            elif isinstance(ra,TableSegment):
                'recursion terminated'               
            else:
                raise InvalidRA
            return ra
        ra = movedownSelect(ra)
        ra = movedownProjection(ra)
        ra = pruneSelect(ra)
        ra = pruneProjection(ra)
        return ra
    
    def apprLength(self,ra):
        if ra == None:
            return None        
        if isinstance(ra,Projection):
            return self.apprLength(ra.input)
        elif isinstance(ra,Select):
            l = self.apprLength(ra.input)
            if l == None:
                return None
            cnf = ra.condition.toCNF().conditions
            factor = 0.5
            apprs = []
            for dnf in cnf:
                appr = 0
                for atom in dnf:
                    atom = atom.toSimple()
                    if isinstance(atom,TestValue):
                        if atom.op == Ops.EQ:
                            col = self.schema.findColumn(atom.fieldref)
                            tab = self.schema.findTable(col.table)
                            if col.name == tab.primaryKey:
                                appr += 1
                            else:
                                appr += factor*l
                        else:
                            appr += factor*l
                    else:
                        appr += factor*l
                apprs.append(appr)
            appr = min(apprs)
            if appr>l:
                appr = l
            return appr
        
        elif isinstance(ra,Join):
            l = self.apprLength(ra.lefttable)
            r = self.apprLength(ra.righttable)
            if l==None:
                return r
            else:
                if r==None:
                    return l
                else:
                    return min([l,r])
        elif isinstance(ra,Union):
            l = self.apprLength(ra.lefttable)
            r = self.apprLength(ra.righttable)
            if l==None:
                return r
            else:
                if r==None:
                    return l
                else:
                    return l+r                
        elif isinstance(ra,Product):
            l = self.apprLength(ra.lefttable)
            r = self.apprLength(ra.righttable)
            if l==None:
                return r
            else:
                if r==None:
                    return l
                else:
                    return l*r
        elif isinstance(ra,TableSegment):
            seg = self.schema.findSegment(ra.id)
            return seg.length
        else:
            raise InvalidRA        
    
    def allocate(self,ra,outerSite = None):
        if outerSite == None:
            outerSite = self.schema.siteId
        if ra == None:
            return None
        if isinstance(ra,Projection):
            '''
            Projection will be assigned to data source
            '''
            inner = self.allocate(ra.input,outerSite).executionSite
            ra.executionSite = inner
        elif isinstance(ra,Select):
            '''
            Select will be assigned to data source
            '''
            inner = self.allocate(ra.input,outerSite).executionSite
            ra.executionSite = inner
        elif isinstance(ra,Join):
            '''
            Join will be done at site with fewer tuples
            '''
            ll = self.apprLength(ra.lefttable)
            rl = self.apprLength(ra.righttable)
            ls = None
            rs = None
            if ll<rl:
                ls = self.allocate(ra.lefttable,outerSite).executionSite
                rs = self.allocate(ra.righttable, ls).executionSite
            else:
                rs = self.allocate(ra.righttable,outerSite).executionSite
                ls = self.allocate(ra.lefttable, rs).executionSite
            if ls == rs:
                ra.executionSite = ls
            else:
                ra.executionSite = outerSite            
        elif isinstance(ra,Union):
            ls = self.allocate(ra.lefttable,outerSite).executionSite
            rs = self.allocate(ra.righttable,outerSite).executionSite
            if ls == rs:
                ra.executionSite = ls
            else:
                ra.executionSite = outerSite
        elif isinstance(ra,Product):
            ls = self.allocate(ra.lefttable,outerSite).executionSite
            rs = self.allocate(ra.righttable,outerSite) .executionSite           
            if ls == rs:
                ra.executionSite = ls
            else:
                ra.executionSite = outerSite
        elif isinstance(ra,TableSegment):
            '''
            Segment will be assigned to a site that holds it,
            If local site has this segment, the local site will be selected
            otherwise a random site will be selected
            '''
            seg = self.schema.findSegment(ra.id)
            if seg.sites.count(outerSite)>0:
                ra.executionSite = outerSite
            else:
                ra.executionSite = random.choice(seg.sites)
        else:
            raise InvalidRA
        return ra
    
    def getSchema(self):
        return dump(self.schema)
    
    def executeSql(self,sql,debug):
        print("Execute: %s"%sql)
        deb = {}
        deb["sql"] = sql
        deb["schema"] = str(self.schema)
        ra = self.parse(sql)
        deb["beforeExpand"]= str(ra)
        ra = self.expand(ra)
        deb["beforeOptimize"] = str(ra)
        ra = self.optimize(ra)
        deb["afterOptimize"] = str(ra)
        ra = self.allocate(ra)
        t = time.clock()
        result = self.findAndExecute(ra).eval()
        t = time.clock() - t
        deb["time"] = str(t)
        deb["resultLength"] = len(result.data())
        deb["result"] = str(result)
        if debug:
            return deb
        else:
            return result 
    
    def getExecuteDelegate(self,site):
        '''
        get an ExecuterSite instance or RPC Proxy fora given site
          site can be Site class or site Id
        '''        
        if not isinstance(site,Site):
            site = self.schema.findSite(site)
        if site.id == self.schema.siteId:
            'local procedure call'
            return self.execute
        else:
            'remote procedure call'
            uri = site.connection
            def re(ra):
                proxy = xmlrpclib.ServerProxy(parseConn(uri),allow_none = 1)
                return read(proxy.executeRemoteDelegate(dump(ra)))
            return re
    
    def executeRemoteDelegate(self,ra):
        ra = read(ra)
        print("Remote execute call: %s"%ra)
        ret = dump(self.execute(ra).eval())
        print("Finished Remote execute call: %s"%ra)
        return ret;
    def findAndExecute(self,ra):
        '''
        Call this function instead of calling self.execute(ra) 
        '''
        execute = self.getExecuteDelegate(ra.executionSite)
        return execute(ra)
    
    def execute(self,ra):
        'execute a relational algebra expression and return its result'
        
        if ra == None:
            return None
        if isinstance(ra,Projection):
            return self.findAndExecute(ra.input).projection(ra.fields)
        elif isinstance(ra,Select):
            return self.findAndExecute(ra.input).select(ra.condition)
        elif isinstance(ra,Join):
            left = self.findAndExecute(ra.lefttable)
            right = self.findAndExecute(ra.righttable)
            return left.join(ra.leftkey,right,ra.rightkey)
        elif isinstance(ra,Union):
            left = self.findAndExecute(ra.lefttable)
            right = self.findAndExecute(ra.righttable)
            return left.union(right)
        elif isinstance(ra,Product):            
            left = self.findAndExecute(ra.lefttable)
            right = self.findAndExecute(ra.righttable)
            return left.product(right) 
        elif isinstance(ra,TableSegment):
            seg = self.schema.findSegment(ra.id)
            dd = DeferredDataset(self.schema,self.mysql)
            dd._select = []
            for colid in seg.columns:
                col = self.schema.findColumn(colid)
                tab = self.schema.findTable(col.table)
                name = "%s.%s"%(tab.name,col.name)
                dd._select.append((col,name))
            dd._from = [seg]
            dd._where = None
            return dd#.eval()
        else:
            raise InvalidRA
    
    def notifySchemaChanged(self,schema):
        if isinstance(schema,str):
            schema = read(schema)
        self.schema = schema
        self.checkSchema()